/**
 * https://leetcode.cn/problems/integer-break/submissions/590290584/
 * 343.整数拆分
 * medium 2024.12.30
 * 记忆化搜索
 */

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        for(int i=2;i<=n;++i){
            int c=0;
            for(int j=1;j<i;++j){
                c=max(c,max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=c;
        }
        return dp[n];
    }
};